//给定一个长度为 n 的链表 head 
//
// 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。 
//
// 返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点
//，设置 answer[i] = 0 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：head = [2,1,5]
//输出：[5,5,0]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：head = [2,7,4,3,5]
//输出：[7,0,5,5,0]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数为 n 
// 1 <= n <= 104 
// 1 <= Node.val <= 109 
// 
// Related Topics 栈 数组 链表 单调栈 
// 👍 191 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class NextGreaterNodeInLinkedList {
    public static void main(String[] args) {
        Solution solution = new NextGreaterNodeInLinkedList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
    class Solution {
        /**
         * 1.使用一个栈保存节点
         * 2.使用一个单调栈保存可能的最大值
         */
        public int[] nextLargerNodes(ListNode head) {
            Stack<ListNode> stack = new Stack<>();// 存储节点
            Deque<Integer> deque = new ArrayDeque<>();// 维护了一个单调栈，保存可能的最大值
            ListNode temp = head;
            while (temp != null){
                stack.add(temp);
                temp = temp.next;
            }
            int n = stack.size();
            int[] res = new int[n];
            for (int i = n - 1; i >= 0 ; i--) {//倒叙遍历链表
                int val = stack.pop().val;
                while (!deque.isEmpty() && deque.peekLast() <= val) deque.pollLast();// 当前值大就出栈
                if (!deque.isEmpty()) res[i] = deque.peekLast();// 栈不空就赋值
                deque.addLast(val);// 当前值入栈
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}